// https://leetcode.cn/problems/validate-binary-search-tree/

// 题干：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
//      有效二叉搜索树定义如下：节点的左子树只包含小于当前节点的数。
//      节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

// 示例：输入：root = [2,1,3]
//       输出：true

// 碎语：一个二叉搜索数，中序遍历必是一个有序数组
//       递归的时候可以采用全局变量，减少栈帧的消耗

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
    long long prev = LONG_LONG_MIN;
public:
    bool isValidBST(TreeNode* root)
    {
        if (root == nullptr) return true;

        bool retLeft = isValidBST(root->left);
        if (!retLeft) return false; // 剪枝，左边要是不行直接返回false

        // 接下来判断当前节点是否符合搜索二叉数的定义
        bool retCur = true;
        if (root->val <= prev) return false; // 剪枝，中间要是不行直接返回false
        prev = root->val; // 要是中间符合，记得更新prev的值

        return isValidBST(root->right); // 前两个都符合，就看最后一个是否正确了
    }
};

int main()
{
    Solution sol;

    auto root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    cout << sol.isValidBST(root) << " ";
    cout << endl;

    return 0;
}